You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1 Output: [1]
Example 3:
Input: nums = [1,-1], k = 1 Output: [1,-1]
Example 4:
Input: nums = [9,11], k = 2 Output: [11]
Example 5:
Input: nums = [4,-2], k = 2 Output: [4]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
Average Rating: 4.05 (166 votes)
Solution
Approach 1: Use a Hammer (Bruteforce)
Intuition
The straightforward solution is to iterate over all sliding windows
and find a maximum for each window. There are N - k + 1 sliding windows
and there are k elements in each window, that results in
a quite bad time complexity O(Nk).
As you can imagine, this straightforward solution would result in TLE (Time Limit Exceed) exception.
It is correct though, one could start with this solution during the interview and improve it later on.
Implementation
Complexity Analysis
-
Time complexity : O(Nk), where
Nis number of elements in the array. -
Space complexity : O(N−k+1) for an output array.
Approach 2: Deque
Intuition
How one could improve the time complexity? The first idea is to
use a heap, since in a maximum heap heap[0] is always the largest element.
Though to add an element in a heap of size k costs
log(k), that means O(Nlog(k)) time complexity
for the solution.
Could we figure out O(N) solution?
Let's use a deque (double-ended queue), the structure which pops from / pushes to either side with the same O(1) performance.
It's more handy to store in the deque indexes instead of elements since both are used during an array parsing.
Algorithm
The algorithm is quite straigthforward :
-
Process the first
kelements separately to initiate the deque. -
Iterate over the array. At each step :
-
Clean the deque :
-
Keep only the indexes of elements from the current sliding window.
-
Remove indexes of all elements smaller than the current one, since they will not be the maximum ones.
-
-
Append the current element to the deque.
-
Append
deque[0]to the output.
-
-
Return the output array.
Implementation
Complexity Analysis
-
Time complexity : O(N), since each element is processed exactly twice - it's index added and then removed from the deque.
-
Space complexity : O(N), since O(N−k+1) is used for an output array and O(k) for a deque.
Approach 3: Dynamic programming
Intuition
Here is another O(N) solution. The good thing about this
solution is that you don't need any data structures but
array / list.
The idea is to split an input array into blocks of k elements.
The last block could contain less elements if n % k != 0.
The current sliding window with the first element i and the last element j
could be placed inside one block, or in two different blocks.
The situation 1 is simple.
Let's use an array left, where left[j] is a maximum element
from the beginning of the block to index j, direction left->right.
To work with more complex situation 2, let's introduce array right,
where right[j] is a maximum element from the end of the block to index j,
direction right->left. right is basically the same as left,
but in the other direction.
These two arrays together give all the information about
window elements in both blocks.
Let's consider a sliding window from index i to index j.
By definition, element right[i] is a maximum element for window elements
in the leftside block,
and element left[j] is a maximum element for window elements
in the rightside block.
Hence the maximum element in the sliding window is
max(right[i], left[j]).
Algorithm
The algorithm is quite straightforward :
-
Iterate along the array in the direction
left->rightand build an arrayleft. -
Iterate along the array in the direction
right->leftand build an arrayright. -
Build an output array as
max(right[i], left[i + k - 1])foriin range(0, n - k + 1).
Implementation
Complexity Analysis
-
Time complexity : O(N), since all we do is
3passes along the array of lengthN. -
Space complexity : O(N) to keep
leftandrightarrays of lengthN, and output array of lengthN - k + 1.
April 8, 2020 6:42 PM
Another way of explaining the deque method (approach 2): You want to ensure the deque window only has decreasing elements. That way, the leftmost element is always the largest.
July 8, 2019 8:23 AM
Great explanation. Please note that it is misleading to include the output array in the space complexity - this makes solution 2 and 3 seem identical when in fact solution 2 is superior.
Solution 1 takes O(nk) time and O(1) space
Solution 2 takes O(n) time and O(k) space
Solution 3 takes O(n) time and O(n) space.
The optimal solution is 2.
August 13, 2019 1:46 AM
Third solution is brilliant brother.
July 1, 2019 5:41 AM
Wow, when I read this sentence it totally confusese me!!!
"
How one could improve the time complexity? The first idea is to use a heap, since in a maximum heap heap[0] is always the largest element. Though to add an element in a heap of size k costs \log(k)log(k), that means \mathcal{O}(N \log(k))O(Nlog(k)) time complexity for the solution."
Can someone explain this out some more? The first idea is to use a heap. How so?
Last Edit: April 17, 2019 7:31 AM
I think the thought behind solution 2 is monotonous stack/queue, and here Deque is to poll from both head and tail
I don't think the approach 3 meet the description of this question. We are told that You can only see the k numbers in the window which means we should treat it as a data stream instead of a static data list. Therefore we shouldn't do any preprocess on it.
For solution 2, we don't have to explicitly have a different way to keep track of max element, from 1..k and k..n separately. We can combine into same logic.
# init deque and output
deq = deque()
output = [] # initialize
for i in range(k):
clean_deque(i)
deq.append(i)
output.append(nums[deq[0]]) # just add max once after the loop
# build output
for i in range(k, n):
clean_deque(i)
deq.append(i)
output.append(nums[deq[0]])
return output
Shouldn't the heap implementation be O(nk) not O(nlogk) because removing a non maximal element is an O(k) operation? Only the adding of an element is O(logk) in this implementation. Would appreciate it if someone could clarify this.
November 19, 2020 9:34 AM
The second solution is really poorly explained.
Last Edit: March 9, 2019 10:05 AM
The third solution is really elegant. Rewrote in C++.
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (nums.empty()) {
return {};
}
int n = nums.size();
vector<int> left(n, 0), right(n, 0), ans(n - k + 1);
left[0] = nums[0];
right[n - 1] = nums[n - 1];
for (int l = 1; l < n; l++) {
left[l] = l % k ? max(left[l - 1], nums[l]) : nums[l];
int r = n - l - 1;
right[r] = (r + 1) % k ? max(nums[r], right[r + 1]) : nums[r];
}
for (int i = 0; i < n - k + 1; i++) {
ans[i] = max(right[i], left[i + k - 1]);
}
return ans;
}
};
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 03/10/2021 13:11 | Accepted | 368 ms | 189.6 MB | cpp |
| 03/10/2021 13:08 | Wrong Answer | N/A | N/A | cpp |
| 03/10/2021 12:52 | Wrong Answer | N/A | N/A | cpp |
| 03/10/2021 12:51 | Wrong Answer | N/A | N/A | cpp |
| 03/10/2021 12:35 | Wrong Answer | N/A | N/A | cpp |
| 03/10/2021 12:34 | Time Limit Exceeded | N/A | N/A | cpp |
| 03/10/2021 12:33 | Time Limit Exceeded | N/A | N/A | cpp |
| 03/10/2021 12:32 | Wrong Answer | N/A | N/A | cpp |
xxxxxxxxxxclass Solution {public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int>res; list<int>l; for(int j=0,i=0;j<nums.size();j++) { while(!l.empty() && l.back() < nums[j]) l.pop_back(); l.push_back(nums[j]); if(j-i+1 == k) { res.push_back(l.front()); if(nums[i] == l.front()) l.pop_front(); i++; } } return res; }};




